package chapter02;

import java.util.Arrays;

public class IsInterleave97 {
    /**
     * 记忆化搜索
     * cha和chb交错组成后能否得到chs
     * process(pos,aPos,bPos)  cha从下标sPos chb从下标bPos 交错组成能否得到从下标pos开始的chs
     * 前提：sa加sb字符数应该等于s
     * 1).sa.length+sb.length!=s.length
     *      return false
     * 递归条件
     * 1).cha chb chs都已经到达结尾 说明前面都正确匹配
     *   aPos==cha.length&&bPos==chb.length&&pos==chs.length
     *      return true
     * 2).chs已匹配字符长度等于cha加chb已匹配字符长度
     *    pos!=aPos+bPos
     *      return false
     * 2).cha和chb当前字符都不匹配chs当前字符 后续都不匹配
     *   默认前提 pos<chs.length
     *   aPos==cha.length||chs[pos]!=cha[aPos])&&(bPos==chb.length||chs[pos]!=chb[bPos]
     *      return false
     * 3).[pos]可以匹配[aPos]或者[bPos]
     *    res=false
     *    a).aPos<cha.length&&chs[pos]==cha[aPos]
     *      res|=process(pos+1,aPos+1,bPos)
     *    a).bPos<chb.length&&chs[pos]==chb[bPos]
     *      res|=process(pos+1,aPos,bPos+1)
     *    return res
     *  回溯过程会产生重复解 增加缓存数组dp[pos][aPos][bPos]
     */
    char[] chs;
    char[] cha;
    char[] chb;
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length()!=s3.length()){
            return false;
        }
        if(s3.length()==0){
            return s1.length()==0&&s2.length()==0;
        }
        if(s1.length()==0){
            return s2.equals(s3);
        }
        if(s2.length()==0){
            return s1.equals(s3);
        }
        chs=s3.toCharArray();
        cha=s1.toCharArray();
        chb=s2.toCharArray();
        int[][][] dp=new int[chs.length+1][cha.length+1][chb.length+1];
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                Arrays.fill(dp[i][j],-1);
            }
        }
        return process(0,0,0,dp);
    }

    public boolean process(int pos,int aPos,int bPos,int[][][] dp){
        if(dp[pos][aPos][bPos]!=-1){
            return dp[pos][aPos][bPos]==1;
        }
        if(pos!=aPos+bPos+1){
            dp[pos][aPos][bPos]=0;
            return false;
        }
        if(aPos==cha.length&&bPos==chb.length&&pos==chs.length){
            dp[pos][aPos][bPos]=1;
            return true;
        }
        if((aPos==cha.length||chs[pos]!=cha[aPos])&&(bPos==chb.length||chs[pos]!=chb[bPos])){
            dp[pos][aPos][bPos]=0;
            return false;
        }
        boolean res=false;
        if(aPos<cha.length){
            if(chs[pos]==cha[aPos]){
                res|=process(pos+1,aPos+1,bPos,dp);
            }
        }
        if(bPos<chb.length){
            if(chs[pos]==chb[bPos]){
                res|=process(pos+1,aPos,bPos+1,dp);
            }
        }
        dp[pos][aPos][bPos]=res?1:0;
        return res;
    }

    //动态规划
    public boolean isInterleave1(String s1, String s2, String s3) {
        if(s1.length()+s2.length()!=s3.length()){
            return false;
        }
        if(s3.length()==0){
            return s1.length()==0&&s2.length()==0;
        }
        if(s1.length()==0){
            return s2.equals(s3);
        }
        if(s2.length()==0){
            return s1.equals(s3);
        }
        chs=s3.toCharArray();
        cha=s1.toCharArray();
        chb=s2.toCharArray();
        boolean[][][] dp=new boolean[chs.length+1][cha.length+1][chb.length+1];
        dp[chs.length][cha.length][chb.length]=true;
        for(int pos=dp.length-2;pos>=0;pos--){
            for(int aPos=dp[0].length-1;aPos>=0;aPos--){
                for(int bPos=dp[0][0].length-1;bPos>=0;bPos--){
                    if((aPos==cha.length||chs[pos]!=cha[aPos])&&(bPos==chb.length||chs[pos]!=chb[bPos])){
                        dp[pos][aPos][bPos]=false;
                    }else{
                        if(aPos<cha.length&&chs[pos]==cha[aPos]){
                            dp[pos][aPos][bPos]|=dp[pos+1][aPos+1][bPos];
                        }
                        if(bPos<chb.length&&chs[pos]==chb[bPos]){
                            dp[pos][aPos][bPos]|=dp[pos+1][aPos][bPos+1];
                        }
                    }
                }
            }
        }
        return dp[0][0][0];
    }

//    public static void main(String[] args) {
//        System.out.println(new IsInterleave97().isInterleave("aabcc","dbbca","aadbbcbcac"));
//    }
}
